package swardToOffer.struct_4_tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author ChanZany
 * @Date 2021/5/19 19:18
 * @Version 1.0
 * 树的三种典型遍历方式
 * 1. 前序遍历：根节点->左子->右子
 * 2. 中序遍历: 左子->根节点->右子
 * 3. 后序遍历: 左子->右子->根
 * 补充
 * 层次遍历
 */
public class TreeUtil {
    static void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    static void inOrder(TreeNode root) {
        if (root == null) return;
        preOrder(root.left);
        System.out.println(root.val);
        preOrder(root.right);
    }

    static void postOrder(TreeNode root) {
        if (root == null) return;
        preOrder(root.left);
        preOrder(root.right);
        System.out.println(root.val);
    }

    static void LevelTraversal(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.println(cur.val);
            if (cur.left != null) queue.offer(cur.left);
            if (cur.right != null) queue.offer(cur.right);
        }
    }



    /**
     * 构建平衡二叉树
     *
     * @param nums 给定数组
     * @param low  数组下标的起点
     * @param high 数组下标的终点
     * @return
     */
    static TreeNode build(int[] nums, int low, int high) {
        if (low > high)
            return null;/*表示子树为空*/
        /*根节点取数组中间索引所在元素*/
        int mid = (high - low) / 2 + low;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, low, mid - 1);/*构建左子树*/
        root.right = build(nums, mid + 1, high);/*构建右子树*/
        return root;
    }

    static void connectLinkedTree(TreeLinkNode parent, TreeLinkNode left, TreeLinkNode right) {
        parent.left = left;
        parent.right = right;
        left.parent = parent;
        right.parent = parent;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6};
        TreeNode root = build(nums, 0, nums.length - 1);
        preOrder(root);
        System.out.println("--------------------");
        LevelTraversal(root);
    }


}
